Section: New Results

Robustness and Tolerance

Cubic B-spline approximation by curve unclamping

Participants : Xiao-Diao Chen, Weiyin Ma, Jean-Claude Paul.

A new approach for cubic B-spline curve approximation is presented. The method produces an approximation cubic B-spline curve tangent to a given curve at a set of selected positions, called tangent points, in a piecewise manner starting from a seed segment. A heuristic method is provided to select the tangent points. The first segment of the approximation cubic B-spline curve can be obtained using an inner point interpolation method, least-squares method or geometric Hermite method as a seed segment. The approximation curve is further extended to other tangent points one by one by curve unclamping. New tangent points can also be added, if necessary, by using the concept of the minimum shape deformation angle of an inner point for better approximation. Numerical examples show that the new method is effective in approximating a given curve and is efficient in computation [2] .

Computing the Hausdorff distance between two B-spline curves

Participants : Xiao-Diao Chen, Weiyin Ma, Gang Xu, Jean-Claude Paul.

This paper presents a geometric pruning method for computing the Hausdorff distance between two B-spline curves. It presents a heuristic method for obtaining the one-sided Hausdorff distance in some interval as a lower bound of the Hausdorff distance, which is also possibly the exact Hausdorff distance. Then, an estimation of the upper bound of the Hausdorff distance in an sub-interval is given, which is used to eliminate the sub-intervals whose upper bounds are smaller than the present lower bound. The conditions whether the Hausdorff distance occurs at an end point of the two curves are also provided. These conditions are used to turn the Hausdorff distance computation problem between two curves into a minimum or maximum distance computation problem between a point and a curve, which can be solved well. A pruning technique based on several other elimination criteria is utilized to improve the efficiency of the new method. Numerical examples illustrate the efficiency and the robustness of the new method [3] .

Surface area estimation of digitized 3D objects using quasi-Monte Carlo methods

Participants : Yu-Shen Liu, Jing Yi, Hu Zhang, Guo-Qin Zheng, Jean-Claude Paul.

A novel and efficient quasi-Monte Carlo method for estimating the surface area of digitized 3D objects in the volumetric representation is presented. It operates directly on the original digitized objects without any surface reconstruction procedure. Based on the Cauchy-Crofton formula from integral geometry, the method estimates the surface area of a volumetric object by counting the number of intersection points between the object's boundary surface and a set of uniformly distributed lines generated with low-discrepancy sequences. Using a clustering technique, we also propose an effective algorithm for computing the intersection of a line with the boundary surface of volumetric objects. A number of digitized objects are used to evaluate the performance of the new method for surface area measurement [5] .

Reverse Engineering for NC Machining Simulation

Participants : Nabil Anwer, Yi-Jun Yang, Haibi Zhao, Olivier Coma, Jean-Claude Paul.

Reverse engineering for NC Machining simulation is becoming an important component of NC simulation and verification. Design engineers need more accurate and complete CAD model of the simulated machined part for finite element analysis or parametric feature-based modeling for design modification or update. The as-cut or in process geometry should be correctly accessed in the CAD/CAM environment at any stage of the machining process. Few commercial software are addressing the reverse engineering issue and provide robust solutions. Until now, in process CAD models for NC simulation have been created with many drawbacks and inaccurate methods are proposed. Reverse engineering for NC machining simulation based on polyhedral in-process geometry is addressed. Two complementary approaches are presented here. An enriched representation embedded in ”Spring technologies Reverse engineering” or SRE file format enables to convert the polyhedral model to STEP file and a discrete shape recognition and segmentation approach provides a promising issue thanks to discrete differential geometry  [43] .

Projection of curves on B-spline surfaces using quadratic reparameterization

Participants : Yi-Jun Yang, Wei Zeng, Hui Zhang, Jun-Hai Yong, Jean-Claude Paul.

Curves on surfaces play an important role in computer aided geometric design. In this paper, we present a hyperbola approximation method based on the quadratic reparameterization of Bezier surfaces, which generates reasonable low degree curves lying completely on the surfaces by using iso-parameter curves of the reparameterized surfaces. The Hausdorff distance between the projected curve and the original curve is controlled under the user-specified distance tolerance. The projected curve is $G^1$ continuous, where $T$ is the user-specified angle tolerance. Examples are given to show the performance of our algorithm  [64] .

A kind of parametric transform for trimmed surfaces

Participants : Sheng Yang, Jun-Hai Yong.

An approach for a kind of parametric transform is presented for trimmed parametric surfaces. Firstly, the characteristics of trimmed surface before and after parametric transform are evaluated. Then, an algorithm is proposed to adjust the geometric and topological data of a trimmed surface in order to achieve consistency. At last, the trimmed sphere surface is taken as example to further illustrate the algorithm  [63] .

A cell-based algorithm for evaluating directional distances in GIS

Participants : Sheng Yang, Jun-Hai Yong, Jia-Guang Sun, He-Jin Gu, Jean-Claude Paul.

Directional distance is commonly used in geographical information systems as a measure of openness. In previous works, the sweep line method and the interval tree method have been employed to evaluate the directional distances on vector maps. Both methods require rotating original maps and study points in every direction of interest. In this article, we propose a cell-based algorithm that pre-processes a map only once; that is, it subdivides the map into a group of uniform-sized cells and records each borderline of the map into the cells traversed by its corresponding line segment. Based on the pre-processing result, the neighbouring borderlines of a study point can be directly obtained through the neighbouring cells of the point, and the borderlines in a definite direction can be simply acquired through the cells traversed by the half line as well. As a result, the processing step does not need to enumerate all the borderlines of the map when determining whether a point is on a borderline or finding the nearest intersection between a half line and the borderlines. Furthermore, we implement the algorithm for determining fetch length in coastal environment. Once the pre-processing is done, the algorithm can work in a complex archipelago environment such as to calculate the fetch lengths in multiple directions, to determine the inclusion property of a point, and to deal with the singularity of a study point on a borderline  [61] .

A point-in-polygon method based on a quasi-closest point

Participants : Sheng Yang, Jun-Hai Yong, Jia-Guang Sun, He-Jin Gu, Jean-Claude Paul.

This paper presents a numerically stable solution to a point-in-polygon problem by combining the orientation method and the uniform subdivision technique. We define first a quasi-closest point that can be locally found through the uniform subdivision cells, and then we provide the criteria for determining whether a point lies inside a polygon according to the quasi-closest point. For a large number of points to be tested against the same polygon, the criteria are employed to determine the inclusion property of an empty cell as well as a test point. The experimental tests show that the new method resolves the singularity of a test point on an edge without loss of efficiency. The GIS case study also demonstrates the capability of the method to identify which region contains a test point in a map  [62] .

Using diffusion distances for flexible molecular shape comparison

Participants : Yu-Shen Liu, Qi Li, Guo-Qin Zheng, Karthik Ramani, William Benjamin.

Background: Many molecules are flexible and undergo significant shape deformation as part of their function, and yet most existing molecular shape comparison (MSC) methods treat them as rigid bodies, which may lead to incorrect shape recognition. In this paper, we present a new shape descriptor, named Diffusion Distance Shape Descriptor (DDSD), for comparing 3D shapes of flexible molecules. The diffusion distance in our work is considered as an average length of paths connecting two landmark points on the molecular shape in a sense of inner distances. The diffusion distance is robust to flexible shape deformation, in particular to topological changes, and it reflects well the molecular structure and deformation without explicit decomposition. Our DDSD is stored as a histogram which is a probability distribution of diffusion distances between all sample point pairs on the molecular surface. Finally, the problem of flexible MSC is reduced to comparison of DDSD histograms  [50] .

A fast sweeping method for computing geodesics on triangular manifolds

Participants : Song-Gang Xu, Yun-Xiang Zhang.

A wide range of applications in computer intelligence and computer graphics require computing geodesics accurately and efficiently. The fast marching method (FMM) is widely used to solve this problem, of which the complexity is $O(NlogN)$, where $N$ is the total number of nodes on the manifold. A fast sweeping method (FSM) is proposed and applied on arbitrary triangular manifolds of which the complexity is reduced to $O\left(N\right)$. By traversing the undigraph, four orderings are built to produce two groups of interfering waves, which cover all directions of characteristics. The correctness of this method is proved by analyzing the coverage of characteristics. The convergence and error estimation are also presented.

A torus patch approximation approach for point projection on implicit surface

Participants : Xiao-Ming Liu, Lei Yang.

Point projection on an implicit surface is essential for the geometric modeling and graphics applications of it. This paper presents a method for computing the principle curvatures and principle directions of an implicit surface. Using the principle curvatures and principle directions, we construct a torus patch to approximate the implicit surface locally. The torus patch is second order osculating to the implicit surface. By taking advantage of the approximation torus patch, this paper develops a second order geometric iterative algorithm for point projection on the implicit surface. Experiments illustrate the efficiency and less dependency on initial values of our algorithm  [52] .

Shape similarity assessment approach for CAD models based on graph edit distance

Participants : Bin Wang, Dong Li.

This paper proposes a new shape similarity assessment approach for CAD models in Boundary Representation (Brep) based on graph edit distance. A suboptimal computational procedure is performed to find the best alignment between local structures sets of attributed graphs derived from models. Assuming that only a minority of local structures characterize the functionality, we figure out the weight of every local structure in the query model through a training phase, and then evaluate the similarity between two models by calculating the weighted graph edit distance of corresponding attributed graphs. Experiment results show that our method provides solid retrieval performance on a real-world CAD model database  [56] .

Reconstructing 3D objects from 2D sectional views of engineering drawings using volume-based method

Participants : Yamei Wen, Hui Zhang, Zhongmian Yu, Jia-Guang Sun, Jean-Claude Paul.

Sectional views are widely used in engineering practice due to their clear and concise expression. However, it is difficult for computers to understand because of the large numbers of omitted entities and their diversified representations. This paper aims at reconstructing 3D models from 2D sectional views by improving the traditional volume based method. First, we present a two-stage loop searching algorithm to extract desired loops from sectional views. Then, sub-objects are identified by the hint-based feature identification algorithm with an intuitive loop-matching criterion. After that, a model-directed algorithm is proposed to guide the generation of sub-objects which are assembled together to form the final objects. The algorithm can handle full sections, partial sections and offset sections, as well as orthographic views. Multiple sectional views are supported in our algorithm. Moreover, the domain of objects is extended to inclined quadric surfaces and intersecting quadric surfaces with higher order curves. Experiment results show its practicability  [60] .

Conditions for coincidence of two cubic Beziér curves

Participants : Wen-Ke Wang, Hui Zhang, Xiao-Ming Liu, Jean-Claude Paul.

This paper presents a necessary and sufficient condition to judge whether two cubic Beziér curves are coincident. For two cubic Beziér curves whose control points are not collinear, they are coincident if and only if their corresponding control points are coincident or one curve is the reversal of another curve. However, this is not true for the degree that is higher than 3. This paper provides a set of counterexamples of degree 4 [28] .

Registration of point clouds using sample-sphere and adaptive distance restriction

Participants : Yu Meng, Hui Zhang.

Registration of point clouds is a fundamental problem in shape acquisition and shape modeling. In this paper, a novel technique, the sample-sphere method, is proposed to register a pair of point clouds in arbitrary initial positions. This method roughly aligns point clouds by matching pairs of triplets of points, which are approximately congruent under rigid transformation. For a given triplet of points, this method can find all its approximately congruent triplets in $O(knlogn)$ time, where n is the number of points in the point cloud, and $k$ is a constant depending only on a given tolerance to the rotation error. By employing the techniques of wide bases and largest common point set (LCP), our method is resilient to noise and outliers. Another contribution of this paper is proposing an adaptive distance restriction to improve ICP (iterative closest point) algorithm, which is a classical method to refine rough alignments. With this restriction, the improved ICP is able to reject unreasonable corresponding point pairs during each iteration, so it can precisely align the point clouds which have large non-overlapping regions [24] .

Torus/torus intersection

Participants : Xiao-Ming Liu, Chang-Yuan Liu, Jun-Hai Yong, Jean-Claude Paul.

This paper presents a new algorithm for torus/torus intersection. The pre-image of the intersection in the parametric space of one torus is represented by an implicit equation. The pre-image is divided into one-valued function curve segments by characteristic points. The topological feature of these characteristic points is analyzed to obtain the structure of the pre-image. Intersection curves satisfying required precision are found by a self-adaptive refinement method. Experiment results are presented to illustrate the stability and efficiency of the method [21] .

Polyline approach for approximating Hausdorff distance between planar free-form curves

Participants : Yan-Bing Bai, Jun-Hai Yong, Jean-Claude Paul, Xiao-Ming Liu.

This paper presents a practical polyline approach for approximating Hausdorff distance between planar free-form curves. After the input curves are approximated with polylines using recursively splitting method, the precise Hausdorff distance between polylines is computed as approximation of Hausdorff distance between free-form curves, and the error of approximation is controllable. The computation of Hausdorff distance between polylines is based on an incremental algorithm that computes directed Hausdorff distance from a line segment to a polyline. Furthermore, not every segment on polylines contributes to the final Hausdorff distance. Based on the bound properties of Hausdorff distance and continuity of polylines, two pruning strategies are applied in order to prune useless segments. R-Tree structure is employed as well to accelerate the pruning process. We experimented our algorithm on sets of Bezier, B-Spline and NURBS curves respectively, and there are 95% segments pruned on approximating polylines in average. Two comparisons are also presented: One is with an algorithm computing directed Hausdorff distance on polylines by building Voronoi diagram of segments, the other is with equation solving method for computing Hausdorff distance between free-form curves [1] .

Algorithm for orthogonal projection of parametric curves onto B-spline surfaces

Participants : Hai-Chuan Song, Xiao-Ming Liu, Jean-Claude Paul.

This paper proposes an algorithm for calculating the orthogonal projection of parametric curves onto B-spline surfaces. It consists of a second order tracing method with which we construct a polyline to approximate the pre-image curve of the orthogonal projection curve in the parametric domain of the base surface. The final 3D approximate curve is obtained by mapping the approximate polyline onto the base surface. The Hausdorff distance between the exact orthogonal projection curve and the approximate curve is controlled under the user-specified distance tolerance. And the continuity of the approximate curve is ${\epsilon }_T-G^1$, where ${\epsilon }_T$ is the user-specified angle tolerance. Experiments demonstrate that our algorithm is faster than the existing first order algorithms [8] .

Converting sectional views to three orthographic views to reconstruct 3D models

Participants : Fengqing Ding, Hui Zhang, Yamei Wen.

Compared with the CSG-based approach, the Brep-based approach has several advantages to construct 3D models from 2D engineering drawings, such as the structure is simpler and the domain of objects that can be handled is wider. However, this approach cannot handle sectional views directly. In this paper, a new method of converting sectional views to three orthographic views is presented. Firstly, the views which have the same projection direction are merged into one view. If the number of views is two, then a new view will be added according to the coordinate relations. Secondly, elements which have been omitted in sectional views are recovered according to the matching information of the existing edges. Finally, the existing Brep-based approach is used to reconstruct the 3D models. The algorithm can handle full sections, broken-out sections, offset sections as well as two orthographic views. The algorithm has been validated by experiments [15] .

Computing the Minimum Distance between Two Tori

Participants : Xiao-Ming Liu, Chang-Yuan Liu, Qiang Hu, Jun-Hai Yong.

The minimal distance computing between two tori is the basis of their collision detection and intersection. A method is proposed for discriminating three types o f position relationship ( i. e. , inclusion, disjunction and intersection) between two tori, and for computing their minimal distance. This paper proves that the Hausdorff distance between two circles in three-dimensional space can be obtained by computing their collinear normal points, which can be calculated by solving an equation of degree 8. With classification and comparison of the collinear normal points, the minimum distance and the Hausdorff distance between these two circles are obtained. In addition, this paper proves that the position relationship between two tori relates to not only the minimum distance but also the directed Hausdorff distance between their central circles. And then the minimum distance between two tori is calculated. Numerical results are presented to illustrate the stability and efficiency of the method [20] .

Computing the Inner Distances of Volumetric Models for Articulated Shape Description with a Visibility Graph

Participants : Yu-Shen Liu, Karthik Ramani, Min Liu.

A new visibility graph based algorithm is presented for computing the inner distances of a 3D shape represented by a volumetric model. The inner distance is defined as the length of the shortest path between landmark points within the shape. The inner distance is robust to articulation and can reflect well the deformation of a shape structure without an explicit decomposition. Our method is based on the visibility graph approach. To check the visibility between pairwise points, we propose a novel, fast, and robust visibility checking algorithm based on a clustering technique which operates directly on the volumetric model without any surface reconstruction procedure, where an octree is used for accelerating the computation. The inner distance can be used as a replacement for other distance measures to build a more accurate description for complex shapes, especially for those with articulated parts [22] .

An extended schema and its production rule-based algorithms for assembly data exchange using IGES

Participants : Kai-Mo Hu, Bin Wang, Yong Liu, Jing Huang, Jun-Hai Yong.

Assembly data exchange and reuse play an important role in CAD and CAM in shortening the product development cycle. However, current CAD systems cannot transfer mating conditions via neutral file format, and their exported IGES files are heterogeneous. In this paper, a schema for the full data exchange of assemblies is presented based on IGES. We first design algorithms for the pre-and-post processors of parts based on solid model, in which the topologies are explicitly specified and will be referred by mating conditions, and then extend the IGES schema by introducing the Associativity Definition Entity and Associativity Instance Entity defined in IGES standard, so as to represent mating conditions. Finally, a production rule-based method is proposed to analyze and design the data exchange algorithms for assemblies. Within this schema, the heterogeneous representations of assemblies exported from different CAD systems can be processed appropriately, and the mating conditions can be properly exchanged. Experiments on the prototype system verify the robustness, correctness, and flexibility of our schema  [49] .

Robust shape normalization of 3D articulated, volumetric models

Participants : Chao Wang, Yu-Shen Liu, Min Liu, Jun-Hai Yong, Jean-Claude Paul.

3D shape normalization is a common task in various computer graphics and pattern recognition applications. It aims to normalize different objects into a canonical coordinate frame with respect to rigid transformations containing translation, rotation and scaling in order to guarantee a unique representation. However, the conventional normalization approaches do not perform well when dealing with 3D articulated objects. To address this issue, we introduce a new method for normalizing a 3D articulated object in the volumetric form. We use techniques from robust statistics to guide the classical normalization computation. The key idea is to estimate the initial normalization by using implicit shape representation, which produces a novel articulation insensitive weight function to reduce the influence of articulated deformation. We also propose and prove the articulation insensitivity of implicit shape representation. The final solution is found by means of iteratively reweighted least squares. Our method is robust to articulated deformation without any explicit shape decomposition. The experimental results and some applications are presented for demonstrating the effectiveness of our method [27] .

A Robust Efficient Algorithm for Accurate Floating-Point Summation

Participants : Zhi Chen, Bin Wang, Norbert Muller, Hui Zhang, Jun-Hai Yong.

The summation of floating-point numbers is ubiquitous in computer systems, while computation implemented in fixed length floating-point arithmetic may lead to inaccurate result due to rounding error. This paper presents an efficient algorithm which produces a faithful result by combining splitting the mantissa and error-free accumulation. Each summand is split into several parts with limited significant bits, which ensures these parts can be accumulated without rounding error under certain conditions. In the implementation, we discuss how to get exponent of floating-point number quickly, which is key to decide how to split summand. Our method works on computers complying with IEEE 754 standard. The running time of our algorithm is proportional to the size of the input data, according to both analysis and numerical tests [12] .

3DMolNavi: A navigation system for flexible molecular shape retrieval based on histogram and dimensionality reduction

Participants : Yu-Shen Liu, Meng Wang, Jean-Claude Paul.

3DMolNavi is a web-based visualized navigation system developed for intuitively exploring flexible molecular shape retrieval. This system is based on the histogram of Inner Distance Shape Signature (IDSS) for fast retrieving molecules that are similar to a query molecule, and uses dimensionality reduction to navigate the retrieved results in 2D and 3D spaces [23] .

Proving Computational Geometry Algorithms in TLA+2

Participants : Hui Kong, Hehua Zhang, Xiaoyu Song, Ming Gu, Jiaguang Sun.

Geometric algorithms are widely used in many scientific fields like computer vision, computer graphics. To guarantee the correctness of these algorithms, it’s important to apply formal method to them. In this paper, we propose an approach to proving the correctness of geometric algorithms. The main contribution of the paper is that a set of proof decomposition rules is proposed which can help improve the automation of the proof of geometric algorithms. We choose TLA+2, a structural specification and proof language, as our experiment environment. The case study on a classical convex hull algorithm shows the usability of the method [36] .

Multi-resolution mesh fitting by B-spline surfaces for reverse engineering

Participants : Sen Zhang, Zhigang Li, Hui Zhang.

This paper presents a new multi-resolution mesh fitting algorithm, extending the adaptive patch-based fitting scheme where each underlying quadrilateral is recursively subdivided into four sub-patches. In this paper, the $G^1$ continuity constraints, which mainly consist of perpendicular constraints and twist compatibility constraints, are deduced for B-spline patches. In order to construct a unique B-spline patch for each quadrilateral, the mesh vertices are applied in a least-square approximation, and the energy functions associated with a patch are minimized. In contrast to the original algorithm, this paper fits the mesh into B-spline patches instead of Bézier patches with $G^1$ continuity. The B-spline patches make the algorithm have more free control points to be used for optimizing the shape of the quadrilateral patches to achieve higher flexible patch control and less recursive times [42] .

An example-driven symbol recognition approach based on key features in engineering drawings

Participants : Tiantian Guo, Hui Zhang, Yamei Wen.

In this paper, we present an example-driven symbol recognition algorithm based on its key features in CAD engineering drawings. When user provides an example of a specific symbol, the input symbol is analyzed and its features are extracted automatically. Based on the relation representation, the constrained tree with key feature priority can be established for this type of symbol. By this means, the symbol library can be built and expanded automatically in order to handle variety engineering drawings. In the next stage of the recognition processes, we first locate the key feature nodes in drawings, and then find other elements around which satisfy the topology structure of constrained tree. If all the elements and constrains in the tree are found, the symbol object will be recognized. Because of the accurate position, unnecessary matching calculations are greatly reduced. Experimental results validate that our approach is effective [33] .

Automatic generation of canonical views for CAD models

Participants : Kaimo Hu, Bin Wang, Bin Yuan, Junhai Yong.

Selecting the best views for 3D objects is useful for many applications. However, with the existing methods applied in CAD models, the results neither exhibit the 3D structures of the models fairly nor conform to human’s browsing habits. In this paper, we present a robust method to generate the canonical views of CAD models, and the above problem is solved by considering the geometry and visual salient features simultaneously. We first demonstrate that for a CAD model, the three coordinate axes can be approximately determined by the scaled normals of its faces, such that the pose can be robustly normalized. A graph-based algorithm is also designed to accelerate the searching process. Then, a convex hull based method is applied to infer the upright orientation. Finally, four isometric views are selected as candidates, and the one whose depth image owns the most visual features is selected. Experiments on the Engineering Shape Benchmark (ESB) show that the views generated by our method are pleasant, informative and representative. We also apply our method in the calculation of model rectilinearity, and the results demonstrate its high performance [34] .